18_depth_first_search.html

Algorithm: Depth-First Search (DFS)

DFS explores a graph $G=(V, E)$ by traversing as far as possible along any path before backtracking. It naturally utilizes a Stack data structure, usually implemented via recursion.

DFS is essential for analyzing the structure of graphs, particularly:

Detecting cycles (via back edges).
Finding strongly connected components (SCCs).
Generating a topological sort.

Tracking Time and State

DFS tracks the state of each vertex using colors (WHITE, GRAY, BLACK) and records two crucial timestamps for each vertex $u$:

Discovery Time ($\text{disc}[u]$): When $u$ is first visited (color changes to GRAY).
Finish Time ($\text{fin}[u]$): When all descendants of $u$ have been explored and $u$ leaves the recursion stack (color changes to BLACK).

DFS Performance Analysis

The complexity of DFS depends entirely on the graph representation, as the algorithm must traverse every vertex and every edge once.

Representation	Time Complexity	Notes
Adjacency List	$O(n + m)$	Optimal. Time spent is linear to the number of vertices $n$ plus the total number of edges $m$.
Adjacency Matrix	$O(n^2)$	For every vertex $n$, the algorithm must potentially scan $n$ columns/rows, regardless of edge density.

DFS Edge Classification

By tracking discovery and finish times, DFS can classify every edge $(u, v)$ encountered:

Edge Type	Condition	Implication
Tree Edge	$v$ is WHITE	Forms part of the DFS forest.
Back Edge	$v$ is GRAY	Cycle detected: $v$ is an ancestor of $u$.
Forward Edge	$v$ is BLACK, $\text{disc}[u] < \text{disc}[v]$	Connects an ancestor $u$ to a non-child descendant $v$.
Cross Edge	$v$ is BLACK, $\text{disc}[u] > \text{disc}[v]$	Connects two different DFS trees or subtrees.

📝 Interactive Quiz

1. In a directed graph, which scenario immediately indicates the existence of a cycle?

A) Finding a Forward Edge.
B) Finding a Tree Edge.
C) Finding a Back Edge (to a GRAY vertex).
D) Finding a Cross Edge.

Hint: A GRAY vertex is currently in the recursion stack, meaning it's an ancestor.

2. What is the optimal time complexity for DFS on a graph with $n$ vertices and $m$ edges?

A) $O(n^2)$
B) $O(n \log n)$
C) $O(n + m)$
D) $O(m)$

Hint: This complexity is achieved when using an Adjacency List representation.

3. The recursive implementation of DFS implicitly uses which data structure?

A) Queue
B) Stack
C) Heap
D) Hash Table

4. An edge $(u, v)$ is found where $v$ is BLACK and $\text{disc}[u] < \text{disc}[v]$. How is this edge classified?

A) Back Edge
B) Cross Edge
C) Tree Edge
D) Forward Edge

KEY TIPS

💡 Key Tips

Stack Overflow Risk

Recursive DFS can fail on very deep graphs (e.g., a long linked list). An iterative version using an explicit stack is more robust.

Disconnected Graphs

A complete DFS implementation requires a main loop that iterates through all vertices, calling the recursive helper only on WHITE nodes. This ensures all components (trees in the DFS forest) are visited.

Back Edge is Key

For cycle detection in directed graphs, the only thing that matters is finding a back edge. An edge $(u, v)$ is a back edge if node $v$ is currently GRAY, meaning it's an ancestor of $u$ in the current recursion path.